Grokking Google Coding Interview
Rate this course
Ask Author
Contribute
Back to course home

0% completed

Vote For New Content
Introduction
Who Should Take This Course?
Google Easy
Add Binary (easy)
Solution: Add Binary
Valid Mountain Array (easy)
Solution: Valid Mountain Array
Set Mismatch (easy)
Solution: Set Mismatch
Is Subsequence (easy)
Solution: Is Subsequence
Length of Last Word (easy)
Solution: Length of Last Word
Search Insert Position (easy)
Solution: Search Insert Position
Repeated Substring Pattern (easy)
Solution: Repeated Substring Pattern
Monotonic Array (easy)
Solution: Monotonic Array
Count Nodes Equal to Average of Subtree (easy)
Solution: Count Nodes Equal to Average of Subtree
Find the Difference (easy)
Solution: Find the Difference
How Many Numbers Are Smaller Than the Current Number (easy)
Solution: How Many Numbers Are Smaller Than the Current Number
Binary Tree Paths (easy)
Solution: Binary Tree Paths
Find the Difference of Two Arrays (easy)
Solution: Find the Difference of Two Arrays
Merge Strings Alternately (easy)
Solution: Merge Strings Alternately
Reverse a LinkedList (easy)
Solution: Reverse a LinkedList
Gray Code (medium)
Solution: Gray Code
2 Keys Keyboard (medium)
Solution: 2 Keys Keyboard
Arithmetic Slices (medium)
Solution: Arithmetic Slices
Unique Length-3 Palindromic Subsequences (medium)
Solution: Unique Length-3 Palindromic Subsequences
Minimum Difference Between Largest and Smallest Value in Three Moves (medium)
Solution: Minimum Difference Between Largest and Smallest Value in Three Moves
Letter Combinations of a Phone Number (medium)
Solution: Letter Combinations of a Phone Number
01 Matrix (medium)
Solution: 01 Matrix
Maximum Points You Can Obtain from Cards (medium)
Solution: Maximum Points You Can Obtain from Cards
Strobogrammatic Number II (medium)
Solution: Strobogrammatic Number II
Maximum Length of Semi-Decreasing Subarrays (medium)
Solution: Maximum Length of Semi-Decreasing Subarrays
Minimum Area Rectangle (medium)
Solution: Minimum Area Rectangle
Count Unreachable Pairs of Nodes in an Undirected Graph (medium)
Solution: Count Unreachable Pairs of Nodes in an Undirected Graph
Single Number II (medium)
Solution: Single Number II
4Sum II (medium)
Solution: 4Sum II
Furthest Building You Can Reach (medium)
Solution: Furthest Building You Can Reach
Minimizing Array After Replacing Pairs With Their Product (medium)
Solution: Minimizing Array After Replacing Pairs With Their Product
Fair Distribution of Cookies (medium)
Solution: Fair Distribution of Cookies
Find Leaves of Binary Tree (medium)
Solution: Find Leaves of Binary Tree
Rotate Image (medium)
Solution: Rotate Image
Combination Sum (medium)
Solution: Combination Sum
Implement Trie (Prefix Tree) (medium)
Solution: Implement Trie (Prefix Tree)
Number of Islands (medium)
Solution: Number of Islands
Edit Distance (medium)
Solution: Edit Distance
Container With Most Water (Medium)
Solution: Container With Most Water
Meeting Rooms II (medium)
Solution: Meeting Rooms II
Shortest Subarray with Sum at Least K (hard)
Solution: Shortest Subarray with Sum at Least K
Reverse Pairs (hard)
Solution: Reverse Pairs
Nth Magical Number (hard)
Solution: Nth Magical Number
Candy (hard)
Solution: Candy
Arithmetic Slices II - Subsequence (hard)
Solution: Arithmetic Slices II - Subsequence
Burst Balloons (hard)
Solution: Burst Balloons
Sum of Distances in Tree (hard)
Solution: Sum of Distances in Tree
Maximum Score of a Good Subarray (hard)
Solution: Maximum Score of a Good Subarray
Trapping Rain Water (hard)
Solution: Trapping Rain Water
First Missing Positive (hard)
Solution: First Missing Positive
Solution: Search Insert Position

Problem Statement

Given an array nums containing integers in non-decreasing order and integer target, return the index if the target is found. If not, return the index where it can be placed such that the final array elements are in non-decreasing order.

You must solve the problem in time.

Examples

  • Example 1:

    • Input: nums = [2,4,6,8,10], target = 1
    • Expected Output: 0
    • Justification: The target number 1 does not exist in the array but should be inserted at index 0 to keep the array in ascending order.
  • Example 2:

    • Input: nums = [1,3,7,9,11], target = 10
    • Expected Output: 4
    • Justification: The target number 10 is not present in the array. It fits between 9 and 11, making the fourth index (0-based indexing) its rightful position.
  • Example 3:

    • Input: nums = [5,8,12], target = 12
    • Expected Output: 2
    • Justification: The number 12 is present at index 2 in the array.

Solution

To solve this problem, we will employ a binary search approach due to its runtime complexity, which fits the requirement for efficiency. The essence of binary search lies in dividing the search interval in half repeatedly, which significantly reduces the number of comparisons needed to find the target or determine its rightful position. This method works effectively because the input array is already sorted in ascending order, allowing us to make assumptions about where the target might be located.

Initially, we define two pointers representing the search interval's bounds: left at the start and right at the end of the array. In each iteration, we compare the target with the middle element of the search interval. If the target is less than the middle element, we move the right pointer to the middle, narrowing our search to the lower half. If the target is greater, we adjust the left pointer to just past the middle element, shifting our focus to the upper half. This process continues until left meets right, indicating the target's position or insertion point, thereby ensuring that our approach is both efficient and effective.

Step-by-Step Algorithm

  1. Initialize Pointers: Start by initializing two pointers, left and right, to point at the start and end of the array, respectively. left is set to 0, and right is set to the length of the array minus one.

  2. Binary Search Loop: While the left pointer is less than or equal to the right pointer, perform the following steps to narrow down the search for the target or its insertion position:

    • Calculate the middle index, mid, as the average of left and right ((left + right) / 2). To avoid potential overflow, you can use left + (right - left) / 2.
    • Compare the target value with the element at the middle index (nums[mid]).
      • If nums[mid] is equal to the target, then the target is found. Return the mid index as the position where the target exists within the array.
      • If nums[mid] is less than the target, it means the target, if it exists, must be in the right half of the current segment. Update left to mid + 1 to narrow the search to the right half.
      • If nums[mid] is greater than the target, this indicates that the target, if present, is in the left half. Update right to mid - 1 to focus the search on the left half.
  3. Identify Insert Position: If the loop terminates without finding the target (i.e., left > right), it means the target does not exist in the array and should be inserted. At this point, left points to the index where the target should be inserted to maintain the sorted order of the array. Return left as the insertion index.

Algorithm Walkthrough

Let's consider the input: nums = [2,4,6,8,10], target = 1.

  • Step 1: Initialize left = 0 and right = 4 (since the array has 5 elements, and indices start at 0).

  • Step 2: Enter the binary search loop:

    • First Iteration:
      • Calculate mid = (0 + 4) / 2 = 2. nums[2] is 6.
      • Since 6 is greater than 1, update right to mid - 1 = 1.
    • Second Iteration:
      • left is still 0, and right is now 1. Calculate mid = (0 + 1) / 2 = 0 (integer division).
      • nums[0] is 2, which is greater than 1. So, update right to mid - 1 = -1.
    • Third Iteration:
      • Now, both left >right. So, the loop terminates.
  • Step 3: Since the loop has terminated and we did not find the target value of 5, left is at the position where 5 should be inserted to maintain the array's order. In this case, left is 0, indicating that the target number 5 should be inserted at index 2.

Code

Java
Saved to Cloud

. . . .

Complexity Analysis

Time Complexity:

  • The algorithm uses binary search to find the target's position or the insertion point in the array. Since binary search divides the search interval in half at each step, the time complexity is logarithmic.
  • With each comparison, it either finds the target or halves the search range, leading to a maximum of comparisons, where n is the number of elements in the array.

Space Complexity:

The algorithm uses a fixed amount of extra space for variables, regardless of the input size. Therefore, the space complexity is constant, as it does not require additional space that scales with the input size.

Search Insert Position (easy)
Repeated Substring Pattern (easy)
Mark as Completed

On this page

Problem Statement

Examples

Solution

Step-by-Step Algorithm

Algorithm Walkthrough

Code

Complexity Analysis

Time Complexity:

Space Complexity: